package com.mlh.dp.背包问题.a01背包;

/**
 * @author 缪林辉
 * @date 2024/4/19 11:54
 * @DESCRIPTION
 */
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

// 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
// 输出：4
// 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
// 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
public class 一和零 {
    //自己写出
    //但是不知道为什么执行时间会稍长 23ms
    public int method1(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < strs.length; i++) {
            int[] nums=method1Aux(strs[i]);
            for (int j = m; j >=nums[0] ; j--) {
                for (int k = n; k >=nums[1] ; k--) {
                    dp[j][k]=Math.max(dp[j][k],dp[j-nums[0]][k-nums[1]]+1);
                }
            }
        }
        return dp[m][n];
    }
    public int[] method1Aux(String s) {
        int zero=0,one=0;
        for(char a:s.toCharArray()){
            if(a=='1'){
                one++;
            }else{
                zero++;
            }
        }
        return new int[]{zero,one};
    }

    //这个是改进了辅助方法而已 时间降到了17ms
    public int method2(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < strs.length; i++) {
            int one=method2Aux(strs[i]);
            int zero=strs[i].length()-one;
            for (int j = m; j >=zero ; j--) {
                for (int k = n; k >=one ; k--) {
                    dp[j][k]=Math.max(dp[j][k],dp[j-zero][k-one]+1);
                }
            }
        }
        return dp[m][n];
    }
    public int method2Aux(String s) {
        int one=0;
        for(char a:s.toCharArray()){
            if(a=='1'){
                one++;
            }
        }
        return one;
    }

    //只是把01背包一维的限制扩展到两维的限制
    public int practice(String[]strs,int m,int n){
        int[][]dp=new int[m+1][n+1];
        for (int i = 0; i < strs.length; i++) {
            int one=practiceAux(strs[i]);
            int zero=strs[i].length()-one;
            for (int j = m; j >=zero; j--) {
                for (int k = n; k >=one; k--) {
                    dp[j][k]=Math.max(dp[j-zero][k-one]+1,dp[j][k]);
                }
            }
        }
        return dp[m][n];
    }
    public int practiceAux(String str){
        char[] chars = str.toCharArray();
        int count=0;
        for (int i = 0; i < str.length(); i++) {
            if(chars[i]=='1'){
                count++;
            }
        }
        return count;
    }
}
